The 19th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2021)
Invited Track
Session Invited-1
Invited Track I
Conference
2:00 PM
—
4:00 PM EDT
Local
Oct 21 Thu, 1:00 PM
—
3:00 PM CDT
The Gittins Policy in the M/G/1 Queue
Ziv Scully and Mor Harchol-Balter (Carnegie Mellon University, USA)
0
The Gittins policy is a highly general scheduling policy that minimizes a wide variety of mean holding cost metrics in the M/G/1 queue. Perhaps most famously, Gittins minimizes mean response time in the M/G/1 when jobs' service times are unknown to the scheduler. Gittins also minimizes weighted versions of mean response time. For example, the well-known "cμ rule", which minimizes class-weighted mean response time in the multiclass M/M/1, is a special case of Gittins. However, despite the extensive literature on Gittins in the M/G/1, it contains no fully general proof of Gittins's optimality. This is because Gittins was originally developed for the multi-armed bandit problem. Translating arguments from the multi-armed bandit to the M/G/1 is technically demanding, so it has only been done rigorously in some special cases. The extent of Gittins's optimality in the M/G/1 is thus not entirely clear. In this work we provide the first fully general proof of Gittins's optimality in the M/G/1. The optimality result we obtain is even more general than was previously known. For example, we show that Gittins minimizes mean slowdown in the M/G/1 with unknown or partially known service times, and we show that Gittins's optimality holds under batch arrivals. Our proof uses a novel approach that works directly with the M/G/1, avoiding the difficulties of translating from the multi-armed bandit problem.
Signaling Games in Higher Dimensions: Geometric Properties of Equilibrium Partitions
Ertan Kazıklı, Sinan Gezici (Bilkent University, Turkey) and Serdar Yüksel (Queen's University, Canada)
0
Signaling game problems investigate communication scenarios where encoder(s) and decoder(s) have misaligned objectives due to the fact that they either employ different cost functions or have inconsistent priors. We investigate a signaling game problem where an encoder observes a multi-dimensional source and conveys a message to a decoder, and the quadratic objectives of the encoder and decoder are misaligned due to a bias vector. For the scalar case, Crawford and Sobel in their seminal paper, show that under certain technical assumptions an encoding policy must be a quantization policy at any Nash equilibrium. We first provide a set of geometry conditions that needs to be satisfied in equilibrium considering any multi-dimensional source. Then, we consider multi-dimensional sources with independent and identically distributed components and completely characterize conditions under which a Nash equilibrium with a linear encoder exists. In particular, we show that if the components of the bias vector are not equal in magnitude, then there exists a linear equilibrium if and only if the source distribution is Gaussian. On the other hand, for a linear equilibrium to exist in the case of equal bias components, it is required that the source density is symmetric around its mean. Moreover, in the case of Gaussian sources, our results have a rate-distortion theoretic implication that achievable rates and distortions in the considered game theoretic setup can be obtained from their team theoretic counterpart.
Federated Few-Shot Learning with Adversarial Learning
Chenyou Fan (Shenzhen Institute of Artificial Intelligence and Robotics for Society, China) and Jianwei Huang (The Chinese University of Hong Kong, Shenzhen, China)
0
We are interested in developing a unified machine learning framework for effectively training machine learning models from many small data sources such as mobile devices. This is a commonly encountered situation in mobile computing scenarios, where data is scarce and distributed while the tasks are distinct. In this paper, we propose a federated few-shot learning (FedFSL) framework to learn a few-shot classification model that can classify unseen data classes with only a few labeled samples. With the federated learning strategy, FedFSL can utilize many data sources while keeping data privacy and communication efficiency. To tackle the issue of obtaining misaligned decision boundaries produced by client models, we propose to regularize local updates by minimizing the divergence of client models. We also formulate the training in an adversarial fashion and optimize the client models to produce a discriminative feature space that can better represent unseen data samples. We demonstrate the intuitions and conduct experiments to show our approaches outperform baselines by more than 10% in learning benchmark vision tasks and 5% in language tasks.
Federated Learning with Correlated Data: Taming the Tail for Age-Optimal Industrial IoT
Chen-Feng Liu and Mehdi Bennis (University of Oulu, Finland)
0
While information delivery in industrial Internet of things demands reliability and latency guarantees, the freshness of the controller's available information, measured by the age of information (AoI), is paramount for high-performing industrial automation. The problem in this work is cast as a sensor's transmit power minimization subject to the peak-AoI requirement and a probabilistic constraint on queuing latency. We further characterize the tail behavior of the latency by a generalized Pareto distribution (GPD) for solving the power allocation problem through Lyapunov optimization. As each sensor utilizes its own data to locally train the GPD model, we incorporate federated learning and propose a local-model selection approach which accounts for correlation among the sensor's training data. Numerical results show the tradeoff between the transmit power, peak AoI, and delay's tail distribution. Furthermore, we verify the superiority of the proposed correlation-aware approach for selecting the local models in federated learning over an existing baseline.
A Framework for Sustainable Federated Learning
Basak Guler (University of California, Riverside, USA) and Aylin Yener (The Ohio State University, USA)
0
Potential environmental impact of machine learning in large-scale wireless networks is a major challenge for the sustainability of next-generation intelligent systems. Federated learning is a recent framework for communication-efficient training of machine learning models over the data collected, stored, and processed by millions of wireless devices. In this paper, we introduce a sustainable machine learning framework for federated learning, using rechargeable devices that can collect energy from the ambient environment. In particular, we propose a practical federated learning framework that utilizes intermittent energy arrivals for training, with provable convergence guarantees. Our framework can be applied to both cross-device and cross-silo federated learning settings, including federated learning in wireless edge networks and the Internet-of-Things. Our experiments demonstrate that the proposed framework can provide significant performance improvement over the benchmark energy-agnostic federated learning settings.
Session Chair
Javad Ghaderi (Columbia University, USA)
Session Invited-2
Invited Track II
Conference
4:30 PM
—
6:30 PM EDT
Local
Oct 21 Thu, 3:30 PM
—
5:30 PM CDT
Eavesdropping with Intelligent Reflective Surfaces: Threats and Defense Strategies
Francesco Malandrino (CNR-IEIIT, Italy), Alessandro Nordio (CNR-IEIIT, Italy) and Carla Fabiana Chiasserini (Politecnico di Torino, Italy)
0
Intelligent reflecting surfaces (IRSs) have several prominent advantages, including improving the level of wireless communications security and privacy. In this work, we focus on this aspect and design a solution to counteract the presence of passive eavesdroppers overhearing transmissions from a base station towards legitimate users. Unlike most of the existing works addressing passive eavesdroppring, the proposed solution has low complexity, is suitable for scenarios where nodes are equipped with a limited number of antennas, and effectively trades off the legitimate users' data rate for secrecy rate.
Age of Information in Ultra-Dense Computation-Intensive Internet of Things (IoT) Systems
Bo Zhou and Walid Saad (Virginia Tech, USA)
0
In this paper, a dense Internet of Things (IoT) monitoring system for computational intensive applications is studied in which a large number of devices with computing capability preprocess the collected raw status information into update packets and contend for transmitting them to the corresponding receivers, using a carrier sense multiple access (CSMA) scheme. Depending on whether the preprocessing operation completes when each device senses a channel, two policies are considered: Preprocess-then-Sense policy (PtS) and Preprocessing-while-Sensing policy (PwS). Particularly, under policy PtS, each device must complete the preprocessing operation before sensing a channel; while under policy PwS, it performs the preprocessing operation and senses a channel concurrently. Here, for policy PwS, if the preprocessing operation is incomplete while a sensed channel is available to be used, then each device will still occupy the channel by sending dummy bits. For both policies, the closed-form expressions of the average age of information (AoI) are characterized. Then, a mean-field approximation framework with guaranteed accuracy is developed to study the asymptotic performance for the considered system in the large population regime. Simulation results validate the analytical results and show that the proposed mean-field approximation under policy PtS is accurate even for a small number of devices. It is also observed that policy PtS achieves a smaller average AoI than policy PwS, revealing that it is unnecessary for each device to occupy the channel before the preprocessing operation completes.
Transmission Delay Minimization via Joint Power Control and Caching in Wireless HetNets
Derya Malak (Rensselaer Polytechnic Institute, USA), Faruk V. Mutlu, Jinkun Zhang and Edmund M. Yeh (Northeastern University, USA)
1
A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively use the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We devise a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) as determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints. Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use strict quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables, and show that under appropriate conditions, the algorithm converges at a linear rate to the local minima of RCF, under general SINR. We support our analytical findings with results from numerical experiments.
The Case for Small-Scale, Mobile-Enhanced COVID-19 Epidemiology
Fan Yi, Yaxiong Xie and Kyle Jamieson (Princeton University, USA)
0
Our understanding of COVID-19 pandemic epidemiology has many gaps, with many challenges arising on a global scale. This paper looks at the problem at a smaller geographical scale, the extent of the campus of a large organization. Equipped with an asymptomatic testing program and rough location data from the campus wireless network, we make the case that epidemiological models may be informed from this new source of data, which offers fidelity at the temporal resolution of seconds and spatial resolution of a Wi-Fi cell size, in particular for the tasks of pinpointing clusters of cases and contexts of infection transmission. We sketch the design of a system that fuses the two foregoing information streams and explain how the result can be incorporated into standard epidemiological models of communicable disease, both for better parameter estimation in elementary models, as well as for providing spatial inputs into more sophisticated models. We conclude with logistical and privacy considerations we have encountered in an associated ongoing study, to inform similar efforts at other organizations.
Session Chair
Guoliang Xue (Arizona State University, USA)
Made with in Toronto · Privacy Policy · © 2022 Duetone Corp.